// https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv/description
// https://www.jiuzhang.com/problem/best-time-to-buy-and-sell-stock-iv/

class Solution {
public:
    /**
     * @param K: An integer
     * @param prices: An integer array
     * @return: Maximum profit
     */    
    int maxProfit(int K, vector<int> &prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        // 当k >= n / 2时，可退化为无限次交易的问题，我们单独处理这种corner case。
        if (K >= n / 2){
            int res = 0;
            for (int i = 1; i < n; i ++){
                res += max(0, prices[i] - prices[i - 1]);
            }
            return res;
        }
        vector<vector<int>> rec(K + 1, vector<int>(n, 0));
        for (int i = 1; i < K + 1; ++i) {
            int maxDiff = -prices[0]; 
            for (int j = 1; j < n; ++j) {
                // rec[i][j] = rec[i][j - 1];
                // // 如果卖出股票，设是在第m天买入，那么第j天的最大利润就是两天的价格差+最多交易i-1次时第m天的获利。这里的m需要从0遍历到j-1。
                // for (int m = 0; m < j; ++m) // TLE
                //     rec[i][j] = max(rec[i][j], prices[j] - prices[m] + rec[i - 1][m]);

                // 为节省这部分的时间开销，用maxDiff表示：最多交易i-1次时，从第0天到第j-1天最大利润-当天价格的最大值。
                maxDiff = max(maxDiff, rec[i - 1][j - 1] - prices[j - 1]);
                rec[i][j] = max(rec[i][j - 1], prices[j] + maxDiff);
            } 
        }
        return rec[K][n - 1];
    }
};